void solve()
{
  int n;
  cin >> n;

  string s;
  cin >> s;
  s = " " + s;

  KMP f(s);
  int m = sz(s) - 1;
  vvi nex(m + 1, vi(2));
  rep(i, 1, m) {
    int k = i - 1, p = i - 1;
    while (k && s[k + 1] != '(') {
      k = f.nex[k];
    }
    while (p && s[p + 1] != ')') {
      p = f.nex[p];
    }
    if (k < m && s[k + 1] == '(') {
      k++;
    }
    if (p < m && s[p + 1] == ')') {
      p++;
    }
    nex[i][0] = k, nex[i][1] = p;
  }

  // dp[i][j][k] : 左括号剩余i个，匹配了s的j个，是否已经完成匹配过的方案数 
  vvvl dp(n + 2, vvl(m, vl(2)));
  dp[0][0][0] = 1;

  rep(i, 1, 2 * n) {
    vvvl ndp(n + 2, vvl(m, vl(2)));
    rep(j, 0, min(i - 1, n)) {
      rep(k, 0, min(i - 1, m - 1)) {
        rep(t, 0, 1) {
          if (s[k + 1] == '(') {
            if (k + 1 == m) {
              ndp[j + 1][0][1] += dp[j][k][t];
            } else {
              ndp[j + 1][k + 1][t] += dp[j][k][t];
            }
            if (j >= 1) {
              int p = nex[k + 1][1];
              ndp[j - 1][p][t] += dp[j][k][t];
            }
          } else {
            if (j >= 1) {
              if (k + 1 == m) {
                ndp[j - 1][0][1] += dp[j][k][t];
              } else {
                ndp[j - 1][k + 1][t] += dp[j][k][t];
              }
            }
            int p = nex[k + 1][0];
            ndp[j + 1][p][t] += dp[j][k][t];
          }
        }
      }
    }
    dp = ndp;
  }

  Z ans = 0;
  rep(i, 0, m - 1) {
    ans += dp[0][i][1];
  }
  cout << ans;
}